lib/Mi manual de algoritmos/version_world_finals_2009/src/dp/particion_troncos.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textit{\textcolor{Brown}{/*}} \\
   6 \mbox{}\textit{\textcolor{Brown}{\ \ O(n\textasciicircum{}3)}} \\
   7 \mbox{} \\
   8 \mbox{}\textit{\textcolor{Brown}{\ dp[i][j]\ =\ Mínimo\ costo\ de\ partir\ la\ cadena\ entre\ las\ particiones\ i\ e\ j,\ ambas\ incluídas.}} \\
   9 \mbox{}\textit{\textcolor{Brown}{\ */}} \\
  10 \mbox{}\textcolor{ForestGreen}{int}\ dp\textcolor{BrickRed}{[}\textcolor{Purple}{1005}\textcolor{BrickRed}{][}\textcolor{Purple}{1005}\textcolor{BrickRed}{];} \\
  11 \mbox{}\textcolor{ForestGreen}{int}\ p\textcolor{BrickRed}{[}\textcolor{Purple}{1005}\textcolor{BrickRed}{];} \\
  12 \mbox{} \\
  13 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{cubic}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
  14 \mbox{}\ \ \textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{,}\ m\textcolor{BrickRed}{;} \\
  15 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{scanf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d\ \%d"{}}}\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}n\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}m\textcolor{BrickRed}{)==}\textcolor{Purple}{2}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  16 \mbox{}\ \ \ \ p\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  17 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$=}m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  18 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{scanf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d"{}}}\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]);} \\
  19 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  20 \mbox{}\ \ \ \ p\textcolor{BrickRed}{[}m\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ n\textcolor{BrickRed}{;} \\
  21 \mbox{}\ \ \ \ m\ \textcolor{BrickRed}{+=}\ \textcolor{Purple}{2}\textcolor{BrickRed}{;} \\
  22 \mbox{} \\
  23 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  24 \mbox{}\ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  25 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  26 \mbox{}\ \ \ \  \\
  27 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}m\textcolor{BrickRed}{-}\textcolor{Purple}{2}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$>$=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{-\/-}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  28 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ j\textcolor{BrickRed}{=}i\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{;}\ j\textcolor{BrickRed}{$<$}m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}j\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  29 \mbox{}\ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ p\textcolor{BrickRed}{[}j\textcolor{BrickRed}{]-}p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{];} \\
  30 \mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{int}\ t\ \textcolor{BrickRed}{=}\ INT$\_$MAX\textcolor{BrickRed}{;} \\
  31 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ k\textcolor{BrickRed}{=}i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ k\textcolor{BrickRed}{$<$}j\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}k\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  32 \mbox{}\ \ \ \ \ \ \ \ \ \ t\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{min}}\textcolor{BrickRed}{(}t\textcolor{BrickRed}{,}\ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}k\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+}\ dp\textcolor{BrickRed}{[}k\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]);} \\
  33 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  34 \mbox{}\ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+=}\ t\textcolor{BrickRed}{;} \\
  35 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  36 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  37 \mbox{} \\
  38 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{,}\ dp\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{][}m\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{]);} \\
  39 \mbox{}\ \ \textcolor{Red}{\}} \\
  40 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  41 \mbox{}\textcolor{Red}{\}} \\
  42 \mbox{} \\
  43 \mbox{} \\
  44 \mbox{}\textit{\textcolor{Brown}{/*}} \\
  45 \mbox{}\textit{\textcolor{Brown}{\ \ O(n\textasciicircum{}2)}} \\
  46 \mbox{} \\
  47 \mbox{}\textit{\textcolor{Brown}{\ \ dp[i][j]\ =\ Mínimo\ costo\ de\ partir\ la\ cadena\ entre\ las\ particiones\ i\ e\ j,\ ambas\ incluídas.}} \\
  48 \mbox{}\textit{\textcolor{Brown}{\ \ pivot[i][j]\ =\ Índice\ de\ la\ partición\ que\ usé\ para\ lograr\ dp[i][j].}} \\
  49 \mbox{}\textit{\textcolor{Brown}{\ */}} \\
  50 \mbox{}\textcolor{ForestGreen}{int}\ dp\textcolor{BrickRed}{[}\textcolor{Purple}{1005}\textcolor{BrickRed}{][}\textcolor{Purple}{1005}\textcolor{BrickRed}{],}\ pivot\textcolor{BrickRed}{[}\textcolor{Purple}{1005}\textcolor{BrickRed}{][}\textcolor{Purple}{1005}\textcolor{BrickRed}{];} \\
  51 \mbox{}\textcolor{ForestGreen}{int}\ p\textcolor{BrickRed}{[}\textcolor{Purple}{1005}\textcolor{BrickRed}{];} \\
  52 \mbox{} \\
  53 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{quadratic}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
  54 \mbox{}\ \ \textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{,}\ m\textcolor{BrickRed}{;} \\
  55 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Black}{scanf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d\ \%d"{}}}\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}n\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}m\textcolor{BrickRed}{)==}\textcolor{Purple}{2}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  56 \mbox{}\ \ \ \ p\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  57 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$=}m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  58 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{scanf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d"{}}}\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{\&}p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]);} \\
  59 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  60 \mbox{}\ \ \ \ p\textcolor{BrickRed}{[}m\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ n\textcolor{BrickRed}{;} \\
  61 \mbox{}\ \ \ \ m\ \textcolor{BrickRed}{+=}\ \textcolor{Purple}{2}\textcolor{BrickRed}{;} \\
  62 \mbox{} \\
  63 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}m\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  64 \mbox{}\ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  65 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  66 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}m\textcolor{BrickRed}{-}\textcolor{Purple}{2}\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  67 \mbox{}\ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}i\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{-}\ p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{];} \\
  68 \mbox{}\ \ \ \ \ \ pivot\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}i\textcolor{BrickRed}{+}\textcolor{Purple}{2}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{;} \\
  69 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  70 \mbox{}\ \ \ \  \\
  71 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ d\textcolor{BrickRed}{=}\textcolor{Purple}{3}\textcolor{BrickRed}{;}\ d\textcolor{BrickRed}{$<$}m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}d\textcolor{BrickRed}{)}\textcolor{Red}{\{}\ \textit{\textcolor{Brown}{//d\ =\ longitud}} \\
  72 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ j\textcolor{BrickRed}{,}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{(}j\ \textcolor{BrickRed}{=}\ i\ \textcolor{BrickRed}{+}\ d\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{$<$}\ m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  73 \mbox{}\ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ p\textcolor{BrickRed}{[}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{-}\ p\textcolor{BrickRed}{[}i\textcolor{BrickRed}{];} \\
  74 \mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{int}\ t\ \textcolor{BrickRed}{=}\ INT$\_$MAX\textcolor{BrickRed}{,}\ s\textcolor{BrickRed}{;} \\
  75 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ k\textcolor{BrickRed}{=}pivot\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}j\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{];}\ k\textcolor{BrickRed}{$<$=}pivot\textcolor{BrickRed}{[}i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{];}\ \textcolor{BrickRed}{++}k\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  76 \mbox{}\ \ \ \ \ \ \ \ \ \ \textcolor{ForestGreen}{int}\ x\ \textcolor{BrickRed}{=}\ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}k\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+}\ dp\textcolor{BrickRed}{[}k\textcolor{BrickRed}{][}j\textcolor{BrickRed}{];} \\
  77 \mbox{}\ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}x\ \textcolor{BrickRed}{$<$}\ t\textcolor{BrickRed}{)}\ t\ \textcolor{BrickRed}{=}\ x\textcolor{BrickRed}{,}\ s\ \textcolor{BrickRed}{=}\ k\textcolor{BrickRed}{;} \\
  78 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  79 \mbox{}\ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+=}\ t\textcolor{BrickRed}{,}\ pivot\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ s\textcolor{BrickRed}{;} \\
  80 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  81 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  82 \mbox{} \\
  83 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}\%d}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{,}\ dp\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{][}m\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{]);} \\
  84 \mbox{}\ \ \textcolor{Red}{\}} \\
  85 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  86 \mbox{}\textcolor{Red}{\}} \\
  87
  88 } \normalfont\normalsize